#!/usr/bin/python
# -*- coding: utf-8 -*-

import uuid
import logging
from datetime import datetime, timedelta
from google.appengine.ext import webapp, db
from google.appengine.ext.webapp.util import run_wsgi_app
from google.appengine.api.labs import taskqueue
import bts.index
import bts.core
import bts.search
from demo import models

logging.getLogger().setLevel(logging.INFO)

sample_title="This is a sample title with some stopwords and some other text"

sample_body = u"""
What I liked best about my old platform was Lucene - it�s a rock solid search engine, and with the Compass framework it integrated very nicely with my object model and application server.  On Google App Engine, I don�t have the ability to run a standalone search engine, so I had to look for an alternative.  The first time I looked at App Engine, I hadn�t found anything comparable, so this was a potential show stopper.  For the record - using an external service like Google Custom Site Search is out of the question, because I need my index to be updated quickly and to integrate very directly with my object model.

I could go on at length about the irony of a Google application platform not including full-text search and how it�s absolutely necessary that this feature be supported, but others have already done so.  I knew that I would need to address this problem now, so I started looking for solutions.

After some research, I ended up with three options: SearchableModel, GAE Search, or something home-grown. I ended up going with the home-grown approach, and here�s why �

GAE Search is basically an improved version of SearchableModel, so it�s the one I looked at most closely.  After playing around with it for a bit, I discovered a few key limitations that I would have known about earlier if I had just read the documentation.

SearchableModel and GAE Search work on the same principle, which is to take all of the keywords derived from indexing a particular model object and store them as a list associated with that object.  For example, let�s say that we have an object (MyModel) with a single indexed property called �description� and an unindexed property called �category�.

MyModel
category = db.StringProperty()
description = db.TextProperty()

When GAE Search indexes this object, it extracts keywords from the description and stores them in a list associated with the object (either on the object itself or in a separate model object with a reference back to the original).  For this example, we�ll assume that it uses the former approach, leaving us with an object that looks like this:

MyModel
category = db.StringProperty()
description = db.TextProperty()
keywords = db.StringListProperty()

Now, in order to perform a query such as �searchword� against this index, GAE Search will construct a datastore query as follows (I�m ignoring stemming for simplicity�s sake).

MyModel.all().filter(�keywords =�, �searchword�)

Seems simple enough, but this approach has two severe disadvantages:

Multi-word queries require additional Datastore indexes
Let�s say that we want to search for �searchword� and get results only in category �The Category�.  This would lead to a query like the below:

MyModel.all().filter(�keywords =�, �searchword�).filter(�category =�, �The Category�)

To support this query, we need to define the below index:

- kind: mymodel
properties:
- name: keywords
- name: category

But what happens if we want to run a simple and query with two words, like �searchwordA searchwordB�?  Well, the query looks like this:

MyModel.all().filter(�keywords =�, �searchwordA�).filter(�keywords =�, �searchwordB�).filter(�category =�, �The Category�)

To support this query, we need to define a new index:

- kind: mymodel
properties:
- name: keywords
- name: keywords
- name: category

As we add more words to the query, we need to create more and more indexes.  Now, imagine adding a few different permutations of sort orders and additional filters, and you can see that this quickly gets out of hand.

Model objects are limited to 1000 terms
Because the terms are stored in a list associated with the object, and because list properties in the App Engine datastore are limited to a length of 1000 items, this means that the full-text index is limited to 1000 terms per object.  For objects that represent large documents, this is a very real and problematic limitation.

How my home-grown approach solves these problems
The fundamental issue with the existing solutions is that they all follow the same anti-pattern, namely storing keywords with the indexed document itself.  This set me to wondering how real search engines like Lucene do it.  Thankfully, I stumbled across a series of articles from Tim Bray that answer this question quite nicely.  The bottom line is that performant full-text search is built using an inverted index.

The question then was, how to implement this on the App Engine and allow filtering and sorting by properties other than those that are indexed?  To explain my solution, I�ll use an enhanced version of our earlier example:

MyModel(db.Model)
category = db.StringProperty()
metropolitan_area = db.StringProperty()
description = db.TextProperty()

This model has three properties, one of which is actually indexed in our full-text index (description) and the other two of which are low-cardinality properties that help to classify the object.  By low-cardinality, I mean that category and metropolitan_area have a limited and fairly small number of discrete values that they can take.

To index MyModel, we�ll need an index object that looks like this:

MyModelIndex(db.Model)
keyword = db.StringProperty()
document_keys = db.ListProperty(db.Key)
category = db.StringProperty()
metropolitan_area = db.StringProperty()

MyModelIndex represents an entry in our inverted index.  The entry contains the following:

keyword -  the indexed keyword (e.g. �searchwordA�)
document_keys - a list of references to documents containing this keyword. This is limited to 1000 entries, but if the same keyword appears in more than 1000 documents, we can simply write multiple entries of MyModelIndex with the same keyword. This is somewhat less efficient than a traditional inverted index, but as long as the number of documents per term doesn�t become too big, I�m not too concered about this.
category and metropolitan_area - any properties on which we need to be able to filter when performing a search are carried over into the index.  This means that if the same keyword appears in documents with different values for these filter properties, we�ll need multiple entries in the index for each distinct combination of filters.  This increases the size of our index, but allows us to filter and sort on these properties and should be manageable so long as these filter properties are of low cardinality.

Now, to search for �searchword� and filter by category �The Category�, we end up with two queries:

MyModelIndex.all().filter(�keyword =�, �searchword�).filter(�category =�, �The Category�)

� then to find the actual objects we union the values of the document_keys property for all of the returned index entries and run the following query �

MyModel.get(unioned_document_keys)

The Datastore index for this looks as follows:- kind: mymodelindex
properties:
- name: keyword
- name: category

So what happens if we want to run the same search, but now with �searchwordA searchwordB�?

Well, we end up running one more query:

MyModelIndex.all().filter(�keyword =�, �searchwordA�).filter(�category =�, �The Category�)
MyModelIndex.all().filter(�keyword =�, �searchwordB�).filter(�category =�, �The Category�)

We would accept all document_keys that appear both in the first and second queries and then pass these to the below query:

MyModel.get(anded_document_keys)

For pagination, we can slice off subsets of the anded_document_keys so that we only retrieve the MyModel objects that we actually need.

You�ll note that this query doesn�t require any new indexes. In fact, we could search for as many words as we like, and the only difference would be how many queries we run against the index.

As far as the anticipated performance characteristics of this approach, I haven�t done much testing but I would expect the following:

   1. The index entries themselves are relatively lightweight compared to the documents themselves, so reading these should be comparatively cheap.
   2. As long as the queries are reasonably selective (i.e. each individual keyword doesn�t appear in too many documents), the overhead of performing ands and ors in memory should be manageable. We can help ensure this by aggressively removing stopwords like �a�, �in�, etc.
   3. If we store the index entries without any common ancestor, the datastore should be able to read them very quickly since they can be stored separately.

I�ve done some basic testing at relatively low volumes, and the approach has held up okay.  Before going too far with this, I�ll want to do some more thorough performance profiling.  If all goes well, this may be a solution that can be offered to the community as a workable search implementation on App Engine until Google provides something more native.

Relative to Lucene, this is all extremely primitive, but it should work well enough for now.
"""
    

#
#Pellentesque placerat eros metus. Suspendisse nec tortor justo. Nulla facilisi. In imperdiet condimentum neque dapibus porttitor. Nulla facilisi. Nullam mattis enim ac mauris scelerisque id venenatis augue condimentum. Quisque lacinia massa eu risus varius rhoncus sit amet in dolor. Nunc at nibh id eros vulputate varius. Sed id ante id mauris mattis tempor. Proin sodales sapien vitae mauris dictum rhoncus. Aliquam vel gravida nisi. Nam vehicula fermentum velit ac fringilla. Morbi pellentesque convallis viverra. Fusce augue justo, eleifend at tincidunt vel, ultrices quis orci. Donec scelerisque mattis suscipit.
#
#Ut neque ligula, malesuada ut faucibus id, viverra ut dui. Curabitur vehicula accumsan risus. Nunc sem leo, accumsan quis luctus at, tristique eget nulla. Proin convallis augue ut orci luctus ullamcorper. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Maecenas congue, augue in accumsan placerat, nibh odio ultrices magna, sit amet consectetur eros odio quis enim. Morbi sed consequat orci. Vestibulum congue mattis odio, vitae tristique arcu tincidunt eget. Vestibulum congue mollis ultrices. Nulla tempor ligula eu orci viverra fringilla. Donec ut augue at leo pellentesque laoreet vitae sit amet dolor. Suspendisse lacinia placerat venenatis. Praesent non elit diam. Nulla volutpat, ipsum sit amet adipiscing venenatis, tellus sapien elementum libero, non fringilla purus augue at erat. Ut a nulla elit, et congue nulla. Suspendisse et neque felis, vel scelerisque turpis. Nam vel eros nisi. Donec at quam at neque dapibus lacinia. Nam sit amet arcu sem.
#
#Vivamus sit amet est arcu, sed ultrices purus. Nulla vitae turpis in lacus ultrices imperdiet. Integer congue, mauris pulvinar venenatis tempor, mi orci convallis justo, id condimentum leo elit a urna. Integer tortor sem, adipiscing a fringilla et, mollis quis ante. Vivamus ac libero lorem, id dapibus libero. Maecenas sed ultrices nisi. Maecenas ut nulla erat. Suspendisse eros orci, bibendum ut cursus vitae, dignissim in leo. Aliquam tincidunt metus sed neque eleifend viverra. Cras eget magna ac nisl convallis pretium. Nam aliquet accumsan elit a vestibulum. Vivamus auctor nibh in turpis egestas quis vestibulum nunc sollicitudin. Lorem ipsum dolor sit amet, consectetur adipiscing elit.
#
#Suspendisse potenti. Phasellus ac odio vel nulla ullamcorper placerat. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Proin gravida volutpat felis id blandit. Vestibulum euismod vestibulum ultrices. Phasellus ultricies dictum euismod. Proin magna erat, molestie at ultricies non, convallis eu dui. Maecenas vitae quam mi, a malesuada nunc. Phasellus et purus ac dui fermentum feugiat et quis quam. Vivamus ipsum quam, dignissim a fringilla et, varius a dui. Sed blandit diam et sem bibendum vestibulum. Sed scelerisque nibh vel est malesuada gravida. Nulla non ligula eros, eget suscipit tortor. Vestibulum quis mi nibh. Donec ac elit id elit semper viverra sed non enim. Donec tortor ante, vestibulum id convallis vel, ornare in felis. In eu nibh eget dolor tincidunt fermentum.
#
#In consequat ornare tincidunt. Nullam eget eros ut sem tincidunt suscipit ac in neque. Proin porttitor orci sed arcu congue congue. Nulla tincidunt, lorem ut porta dictum, turpis lorem ullamcorper libero, a semper purus orci id ante. Nam volutpat libero et lectus tempus adipiscing. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Pellentesque condimentum tellus ac lorem bibendum ac tempus felis ultricies. Mauris hendrerit, purus vitae interdum tincidunt, justo ipsum vestibulum felis, sit amet convallis velit libero vitae enim. Suspendisse non pretium urna. In mi ipsum, tristique et posuere vitae, viverra sed neque. Aliquam nec metus nec libero adipiscing laoreet. In quis augue libero, in interdum neque. Ut sodales, tellus sit amet posuere tempor, justo quam semper ipsum, quis faucibus leo nisl a metus.
#
#Curabitur luctus tortor at dui pretium vestibulum. Duis nec lorem eget dolor mattis placerat in ut libero. Proin eget cursus elit. Mauris id gravida elit. In quis justo ligula. Curabitur dignissim, purus vitae egestas ullamcorper, felis nulla adipiscing ligula, sit amet interdum sem augue a purus. Cras ac justo auctor est dapibus iaculis. Nullam volutpat dolor at turpis convallis lacinia sollicitudin urna blandit. In luctus fermentum nibh, eu mattis lorem lacinia sed. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Aenean feugiat euismod neque ac sollicitudin.
#
#Nunc suscipit enim in ante lobortis varius eget pellentesque ligula. In ac hendrerit nibh. Suspendisse neque sem, lacinia sagittis sollicitudin vitae, tincidunt a leo. Fusce faucibus lorem sit amet risus adipiscing ultrices. Morbi a arcu quis neque facilisis malesuada in quis nunc. Nullam bibendum, risus porta tristique bibendum, justo justo pretium odio, ut venenatis diam ligula quis magna. Morbi a odio quam. Proin mattis, velit convallis elementum tincidunt, justo nunc dapibus leo, a laoreet nisl odio sit amet mi. Praesent ultrices accumsan vulputate. Nulla facilisi.
#
#Nulla nunc nisi, convallis pretium condimentum sit amet, tempor a neque. Maecenas accumsan varius orci fermentum sollicitudin. Quisque dui turpis, vehicula eget sagittis quis, consequat id ante. Curabitur vehicula mi eu quam pulvinar varius. Duis vel congue est. Nam id ante id ante congue sodales quis sagittis est. Vestibulum faucibus sodales felis, ac bibendum nunc pretium tristique. Maecenas feugiat vehicula dui a dapibus. Nam sed aliquet neque. Suspendisse sollicitudin massa at dui bibendum eu commodo mauris gravida. Nulla facilisi.
#
#Quisque justo nulla, placerat sed fringilla vel, aliquet at quam. Praesent nisl leo, rutrum non mattis vitae, porttitor nec justo. Nullam nec velit velit. Maecenas ut nibh magna, vel dictum mauris. Curabitur mollis euismod interdum. Proin fringilla molestie facilisis. Etiam dignissim feugiat ligula, in tempor magna gravida et. Nunc venenatis rhoncus massa, a dapibus augue placerat at. Donec fermentum tellus non libero rutrum blandit. Proin dignissim condimentum tempor. Ut eget iaculis quam. Fusce sit amet ipsum eget est posuere tristique. Nullam quis lacus sit amet tellus pretium elementum et vitae ligula. In metus metus, ultrices quis vehicula sit amet, condimentum sed sapien. Phasellus vel commodo ipsum. Nullam tortor orci, laoreet non condimentum ac, commodo vitae lorem. Phasellus ultricies condimentum tempor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.
#
#Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras sem ante, euismod non ultrices pellentesque, porttitor sit amet elit. Nulla pharetra velit quis velit ultrices ultrices vitae vel ligula. Fusce id urna vitae mi semper egestas eget et erat. Suspendisse potenti. Nullam sit amet orci id purus rutrum vestibulum. Nunc purus ipsum, fringilla eget tincidunt eu, faucibus non lorem. Nulla viverra eros vitae nisl pharetra nec varius enim viverra. Pellentesque pellentesque dolor nec urna laoreet eget euismod sem blandit. Proin varius magna ut felis fringilla a lacinia odio posuere. Integer cursus elit enim, nec ornare velit. Phasellus tincidunt imperdiet lacinia. Nam id dolor porttitor risus iaculis dapibus vel at dui. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Aenean in lorem eget tellus viverra iaculis vel et tortor. Donec interdum, mi sit amet interdum mollis, dolor libero elementum diam, et accumsan nunc mi eget risus.
#
#Etiam arcu felis, posuere vitae tempus eget, hendrerit eget lectus. Aliquam consectetur neque et ligula porttitor porta. Vivamus egestas nisl sit amet lectus ultricies blandit. Nulla facilisi. Maecenas venenatis porta urna sit amet placerat. Nunc eu eros ut erat tempus tristique. Morbi nec ipsum non tortor hendrerit feugiat eu quis nisl. Aenean feugiat, magna sit amet tempus lobortis, erat nisi pharetra leo, sit amet condimentum neque odio vitae turpis. Maecenas accumsan faucibus ante eu ullamcorper. Nulla euismod dui eget erat lobortis vel feugiat erat consectetur. Maecenas dui mi, porttitor eget convallis non, rutrum quis arcu. Etiam ipsum quam, sagittis sed fringilla at, congue quis erat. Nulla facilisi. Suspendisse ultrices, tortor et tempor commodo, justo enim fringilla arcu, auctor sagittis mauris diam eget tellus.
#
#Ut convallis diam vitae ipsum accumsan at consectetur massa pharetra. Aliquam rutrum magna eget nulla bibendum at porttitor dolor suscipit. Mauris rhoncus egestas est at ornare. Nam enim metus, egestas ac ultricies vitae, interdum quis mauris. Nunc quis libero eros, et consectetur metus. Fusce tempor luctus quam, vel egestas augue blandit eu. Duis sed nulla diam, ut porttitor metus. Cras sagittis ipsum id erat pellentesque ut varius justo blandit. Suspendisse eu libero tortor, eu ultricies nisl. Nullam quam velit, convallis eu imperdiet at, sodales vel lacus. Sed tincidunt aliquet risus, eu cursus augue imperdiet in. Nam eu tellus nunc.
#
#Phasellus luctus mollis dignissim. Curabitur eget felis vel turpis mattis laoreet non eu urna. Donec tristique ultricies rutrum. Proin bibendum lectus eget lectus iaculis imperdiet. Vestibulum fringilla tellus eu enim tincidunt vitae imperdiet lorem mattis. Praesent urna sem, vestibulum eget vehicula eu, commodo et est. Maecenas eget tortor eget metus tincidunt feugiat eu vitae felis. In hac habitasse platea dictumst. Phasellus ultricies ligula sit amet nunc ornare sed scelerisque enim consequat. Curabitur pulvinar mi non odio tincidunt elementum. Integer sapien arcu, cursus sit amet tempus vitae, vestibulum quis enim. Phasellus adipiscing felis ac tortor pellentesque dictum. Nulla tristique ante ultricies velit dictum feugiat. Morbi erat felis, adipiscing et euismod et, gravida et diam. Nulla feugiat lobortis ante, et aliquet purus dapibus tristique. Fusce tempor tincidunt lectus eget tincidunt. Sed convallis aliquet neque. Nulla facilisi.
#
#Vivamus in nisi turpis, ac facilisis metus. Donec odio sapien, faucibus at interdum adipiscing, dapibus vel diam. Donec ac massa et tellus interdum convallis. Nunc dictum diam eu ipsum consectetur porta consequat lacus sodales. Ut vel ligula in velit placerat euismod ut quis metus. Aliquam id egestas orci. Vivamus fermentum scelerisque ipsum, et mollis odio auctor sed. Duis eget neque ligula, eu ornare ante. Aenean iaculis ipsum vel lorem interdum nec semper dolor iaculis. Suspendisse eros sem, sollicitudin vel volutpat scelerisque, luctus ut tortor. Duis erat justo, varius in vestibulum ac, aliquet id urna. Ut et felis eu risus interdum congue. Nunc adipiscing magna ac massa scelerisque quis luctus nunc molestie. Nunc pretium viverra semper. Aliquam porttitor urna eget eros condimentum venenatis. Cras vehicula, enim quis tristique vestibulum, odio lorem venenatis magna, id lacinia nulla lectus non felis.
#
#Nullam malesuada placerat convallis. Phasellus molestie, mauris vel tempor porta, justo orci scelerisque dolor, in aliquet quam est ac enim. Fusce et rhoncus nulla. Ut tincidunt tristique posuere. Donec purus ipsum, suscipit a convallis nec, suscipit eu metus. Pellentesque at lorem massa. Morbi nec libero elit. In hac habitasse platea dictumst. Duis aliquet porttitor nisi, fringilla gravida diam volutpat eget. Nam hendrerit mauris imperdiet tellus consectetur nec ultricies diam lobortis. Proin lacinia, augue a fringilla placerat, ligula leo condimentum sem, sed scelerisque leo ipsum ut nisi. Nam pharetra ipsum quis mi elementum a mollis elit congue. Phasellus vel odio orci, ut porta nisi. Sed eget mauris felis. Duis pellentesque, enim vitae accumsan condimentum, enim risus dictum elit, posuere auctor felis est a quam.
#
#Vivamus a justo malesuada velit egestas adipiscing ornare vitae nisl. Fusce faucibus, mi in congue fermentum, felis ante varius nisi, a imperdiet arcu libero id turpis. Integer vitae odio enim. Proin dui odio, lacinia eget porta vitae, adipiscing nec tellus. Etiam vitae tortor vitae odio commodo convallis a hendrerit risus. Morbi vulputate aliquet tellus, et consectetur ligula suscipit sed. Sed justo urna, condimentum.
#"""

def delete_all(start_time, type):
    keys = None
    count = 0
    while (datetime.now() - start_time < timedelta(seconds=20
            )) and (keys == None or len(keys) > 0):
        keys = type.all(keys_only=True).fetch(100)
        db.delete(keys)
        count += len(keys)
    return count

class LoadTestData(webapp.RequestHandler):
    def post(self):
        topics = []
        for name in ['An Important Topic', 'A Less Important Topic',
                     'A Minor Topic']:
            topic = models.Topic.all().filter('name =', name).get()
            if not topic:
                topic = models.Topic(name=name)
                topic.put()
            topics.append(topic)
        number_of_topics = len(topics)
        number_of_posts = int(self.request.get('number_of_posts'))
        posts = []
        for i in range(0, number_of_posts):
            posts.append(
                    models.BlogPost(topic=topics[i % number_of_topics],
                                    title=sample_title, body=self.request.get("body_text")))
        db.put(posts)
        for post in posts:
        # If using django, you can use the update signal to do this automatically
            bts.index.request_indexing(post)
        self.response.headers['Content-Type'] = 'text/plain'
        self.response.out.write('Created %s sample posts' % number_of_posts)

class Search(webapp.RequestHandler):
    def get(self):
        self.response.headers['Content-Type'] = 'text/html'
        query_string = self.request.get('query_string')
        topic = None
        topic_name = self.request.get('topic')
        if topic_name:
            topic = models.Topic.all().filter('name =', topic_name).get()
        start_time = datetime.now()
        query = bts.search.query(models.BlogPost)
        query.filter_fulltext(query_string)
        if topic:
            query.filter("topic =", topic)
        results = query.fetch(int(self.request.get('limit')), 0)
        query_time = datetime.now()
        time_for_query = query_time - start_time
        available_results = query.count()
        number_of_results = len(results)
        self.response.out.write("<html><body>")
        start_time = datetime.now()
        facet = query.facet("topic")
        query_time = datetime.now()
        facet_time_for_query = query_time - start_time
        self.response.out.write("<u>Available Topics (facets retrieved in %s)</u><br/>" % facet_time_for_query)
        for topic, frequency in facet.iteritems():
            self.response.out.write("%s - %s<br/>" % (topic.name, frequency))
        self.response.out.write("<br/><u>Results (%s of %s available retrieved in %s)</u><br/>" % (number_of_results, available_results, time_for_query))
        for result in results:
            self.response.out.write('<h3>%s (%s)</h3><pre>%s</pre><br/>' % (result.title, result.key(), result.body))
        self.response.out.write("</body></html>") 

class Drop(webapp.RequestHandler):
    def get(self):
        start_time = datetime.now()
        delete_all(start_time, bts.models.TermHits)
        delete_all(start_time, bts.models.TermUpdate)
        delete_all(start_time, bts.models.ModelTerms)
        delete_all(start_time, models.BlogPost)
        delete_all(start_time, models.Topic)
        self.response.out.write("Dropped all data")

application = webapp.WSGIApplication([('/demo/load-test-data', LoadTestData),
                                      ('/demo/search', Search),
                                      ('/demo/drop', Drop)],
                                     debug=False)

def main():
    run_wsgi_app(application)

def profile_main():
    # This is the main function for profiling 
    # We've renamed our original main() above to real_main()
    import cProfile, pstats, StringIO
    prof = cProfile.Profile()
    prof = prof.runctx("main()", globals(), locals())
    stream = StringIO.StringIO()
    stats = pstats.Stats(prof, stream=stream)
    stats.sort_stats("time")  # Or cumulative
    stats.print_stats(80)  # 80 = how many to print
    # The rest is optional.
    # stats.print_callees()
    # stats.print_callers()
    logging.info("Profile data:\n%s", stream.getvalue())
    
if __name__ == "__main__":
    profile_main()